package 笔试.华为.线下面试;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class a210课程表2 {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int numCourses = 3;
        int[][] prerequisites = {{1, 0}, {1, 2}, {0, 1}};
        System.out.println(Arrays.toString(solution.findOrder(numCourses, prerequisites)));
    }

    static class Solution {
        public int[] findOrder(int numCourses, int[][] prerequisites) {
            ArrayList<Integer>[] matrix = new ArrayList[numCourses];
            for (int i = 0; i < matrix.length; i++) {
                matrix[i] = new ArrayList<>();
            }
            int[] inDegree = new int[numCourses];
            for (int i = 0; i < prerequisites.length; i++) {
                int x = prerequisites[i][0];
                int y = prerequisites[i][1];
                matrix[y].add(x);
                inDegree[x]++;
            }
            Queue<Integer> queue = new LinkedList<>();
            for (int i = 0; i < numCourses; i++) {
                if (inDegree[i] == 0) {
                    queue.add(i);
                }
            }
            ArrayList<Integer> list = new ArrayList<>();
            while (!queue.isEmpty()) {
                Integer poll = queue.poll();
                list.add(poll);
                for (Integer target : matrix[poll]) {
                    inDegree[target]--;
                    if (inDegree[target] == 0) {
                        queue.add(target);
                    }
                }
            }
            return list.size() == numCourses ?
                    new int[0] :
                    list.stream().mapToInt(i -> i).toArray();
        }
    }
}
